1. Field of the Invention
The present invention relates to an optimizing device for code optimization in the compiler and particularly relates to a compiler optimizing device which makes optimization by transfer of the loop invariant expressions and the method therefor.
2. Description of the Related Art
In general, the compiler is widely used in the field of software development as the translation program for programming languages. To generate the object code with a faster execution speed, various optimization methods have been proposed. One of them is the method to move the loop invariant expressions.
Many of the programming languages allow description of repeated processes called the loop statements. In loop statements, the programmer, with attaching greater importance to the readability of the program, sometimes describes the expressions which generate the same result even after repetition in the loop, i.e. loop invariant expressions. Since it is sufficient for such invariant expressions to be processed once, they can be taken out of the loop statements. Therefore, by transferring the loop invariant expressions described in the source program by the programmer out of the loop statements during compilation, redundant repetitions are reduced and the object code with a faster execution speed can be generated. Thus, the code can be optimized by appropriately transferring the loop invariable expressions.
In programming languages, however, programs are usually designed with modules and, according to their specification, a series of processes are grouped as a functional unit called a function and such function can be arbitrarily called from the program. The conventional optimization method to move the loop invariant expressions could not recognize which variable in a function had been changed upon function call in the loop. It could not recognize the expressions with the same result after repetition in the loop, and it was impossible to move the loop invariant expressions in the loop statements including function calls.
In addition, programming languages allow description of branch execution with conditional expressions called the conditional statements. However, such description may include branch processing which is not executed depending on the condition and, usually, the expressions in the conditional statements are not transferred.
A conventional optimization method which optimizes the code by transferring the loop invariant expressions as mentioned above is, for example, disclosed in the reference "Compiler (Information Processing Series 7)" (written by A. V. Eiho and J. D. Urman and translated by Norihisa Doi, Baifukan, 1986, pp. 5-7 and FIGS. 1 and 2). FIG. 25 is a block diagram to show the configuration of an optimizing device which embodies the conventional optimization method described in the above reference.
A conventional optimizing device shown in FIG. 25 comprises a lexical analysis section 10 which decomposes the source program into lexical units, a syntactic analysis section 20 which, upon receipt of the lexical analysis result, makes syntactic analysis, an optimizing section 130 including a loop invariant expression transfer section 131 which, upon receipt of the syntactic analysis result, transfers the loop invariant expressions out of the loop, and a code generation section 70 which, upon receipt of the optimization result, generates the object code.
Next, referring to FIG. 25, the operation of a conventional compiler optimizing device is described below. The lexical analysis section 10 receives the source program supplied from outside and makes the lexical analysis to decompose such source program into lexical units. The syntactic analysis section 20 receives the lexical analysis result from the lexical analysis section 10 and constructs and recognizes the syntax. Then, the loop invariant expression transfer section 131, which is a component of the optimizing section 130, receives the syntactic analysis result, detects the invariable expressions movable in the loop i.e. the loop invariable expressions and transfers them out of the loop. Finally, the code generation section 70 receives the optimization result and generates the object code.
FIG. 27 is a flowchart to show the processing procedure of the loop invariable expression transfer section 131. Referring to the figure, the loop invariant expression transfer section 131 extracts the invariant variables from the loops, checks for any change in values caused by reference, assignment and repetition and registers the data to a loop variable status table 410 as shown in FIG. 26. Then, it detects the invariant expressions based on the data registered to such loop variable status table and transfers them out of the loops.
Referring to FIG. 26, the loop variable status table 410 generated in processing by the loop invariable expression transfer section 131 is provided with four areas: a variable name column 411 to fill in the variable names of the variables constituting the expressions in the loop statements, a reference column 412 to fill in the data indicating that the applicable variable is referenced when it is referenced (value "1", for example), an assignment column 413 to fill in the data indicating that the applicable variable is assigned when it is assigned (value "1", for example), and a change column 414 to fill in the data indicating that the value possibly changes for every repetition due to assigned variable (value "1", for example).
Then, referring to FIG. 27, the processing procedure by the loop invariant expression transfer section 131 is described below.
Firstly, a certain syntax file is opened (Step 2701). Next, a syntax for one line is read (Step 2702). Then, it is judged whether the syntax represents the end of syntax file (Step 2703). If it is the end of syntax file, the syntax file is closed and the processing is terminated (Step 2711). If it is not the end of syntax file, it is judged whether the read syntax is leading loop statements or not (Step 2704). If it is not, the processing returns to Step 2702. If it is leading loop statements, flag F to be used for identification of whether or not any function call is made in the loop statements is initialized with "0" (Step 2705).
Next, all items of the variable name column 411, the reference column 412, the assignment column 413 and the change column 414 on the loop variable status table 410 are initialized with "0" (Step 2706). Then, the variables whose values do not change even after repetition in the loop statements, i.e. the invariant variables are detected (Step 2707). At this Step, the variables constituting the expressions in the loop are checked to see whether reference or assignment is made. Necessary data are filled in to the columns for variable name 411, reference 412 and assignment 413 on the loop variable status table 410. Since a variable subjected to assignment after reference has different values for the first repetition and the repetition from the second time, the change column 414 is also filled in with the indication data.
Referring to the flowchart of FIGS. 28 and 29, the procedure of the invariant variable detection (Step 2707) is described below.
Firstly, a recognition flag I to indicate that a conditional statement is being processed is initialized with "0" (Step 2801). Next, a syntax for one line is read (Step 2802). Then, it is judged whether the read syntax represents the end of loop statements (Step 2803). If the read statement represents the end of loop statements, the invariant variable detection is terminated.
If the read statement does not represent the end of loop statements, then it is judged whether the read syntax is a function call statement (Step 2804). If it is a function call statement, the loop invariant expression cannot be moved. In this case, a flag F to indicate that a function call is made in the loop statements is set to "1" and the invariant variable detection step 280 is terminated (Step 2810).
If the read syntax is not a function call, it is judged whether the read syntax is at the beginning of conditional statements (Step 2805). If it is not at the beginning of conditional statements, processing is proceeded to Step 2806. On the other hand, if it is at the beginning of conditional statements, the expressions in the conditional statements may not be executed. In this case, after incrementing the flag I indicating that the conditional statement is being processed by "1" (Step 2811), processing is proceeded to Step 2806.
Next, it is judged whether the read syntax represents the end of conditional statements (Step 2806). If it does not represent the end of conditional statements, then the processing proceeds to Step 2807. On the other hand, if it represents the end of conditional statements, the flag I to indicate that the conditional statement is being processed is decremented by "1" before proceeding to Step 2807.
Then, a flag S to indicate that the syntax currently being processed is an expression for reference only is initialized with "0" (Step 2807) and it is judged whether or not the read syntax is an expression for reference only (Step 2808). If the expression is for reference only, it does not contain any variable for assignment. In this case, the reference expression flag S for judgment whether or not processing for assignment expression is required is set to "1" (Step 2813). In the procedure from Step 2814, data are registered to the loop variable status table 410 and the loop variable status table is arranged to fill in the data of reference, assignment and change for the variables in the expressions.
If the read syntax is not an expression for reference only, it is judged whether the read syntax is an assignment subject statement for a variable (Step 2809). If it is not an assignment subject statement for a variable, the processing returns to Step 2802. If it is an assignment subject statement for a variable, the loop variable status table is arranged in the procedure from Step 2814.
In the loop variable status table arrangement, the number of variables as the reference subjects in the assignment origin expression is set to a counter N in order to check the number of variables before the invariant variable detection (Step 2814). Then, it is judged whether the counter N has "0" (Step 2815). If it does not have "0", the N-th variable has not been subjected to the invariant variable detection. Then, it is judged whether the variable name of the N-th variable has been registered to the variable name column 411 on the loop variable status table 410 (Step 2816). If the variable name has been registered, the processing is proceeded to Step 2817. If not, the variable name of the N-th variable is registered to the variable name column 411 of the loop variable status table 410 (Step 2824) and the processing is proceeded to Step 2817. The value "1", is entered to the reference column 412 for the variable name of the N-th variable (Step 2817), the value at the counter N is decremented by "1" and the processing returns to Step 2815 (Step 2818). The above processes are repeated for the remaining variables until the counter N has "0".
If the counter N has "0", it means that there is no variable which has not been subjected to the invariant variable detection, and it is judged whether the reference expression flag S is "0" (Step 2819). If the flag S is not "0", the syntax which is currently being processed is an expression for reference only. In this case, the processing returns to Step 2802 without making any processing for an assignment statement. If the flag S is "0", it is judged whether the assignment destination variable name is registered to the variable name column 411 of the loop variable status table 410 (Step 2820). If it is registered, the processing is proceeded to Step 2821. If it is not, the variable name of the assignment destination variable is registered to the variable name column 411 on the loop variable status table 410 (Step 2825) and the processing is proceeded to Step 2821.
Next, it is judged whether the conditional statement processing flag I is "0" (Step 2821). If it is not "0", the syntax is under processing of the conditional statement. In this case, to prevent transfer of the expression, "1" is entered to the change column 414 for the variable name of the assignment destination variable on the loop variable status table 410 (Step 2826) before return to Step 2802. If the conditional statement processing flag I is "0", then it is judged whether "1" is entered to the reference column 412 or the assignment column 413 for the variable name of the assignment destination (Step 2822). If the reference column 412 or assignment column 413 has "1", such variable may have different values for the first repetition and the repetitions from the second time. To prevent transfer of the expression including the above variable, "1" is entered to the change column 414 for the variable name of the assignment destination variable (Step 2826) before return to Step 2802. If the reference 412 or assignment 413 does not have "1", then "1" is entered to the assignment column 413 for the variable name of the assignment destination variable (Step 2823) before return to Step 2802.
Until arrival at the end of loop statements, the above loop invariant variable detection procedure (Steps 2801 to 2826) is repeated. After it is repeated until the end of loop statements, the processing returns to FIG. 27 and goes to Step 2708.
After detection of invariant variables in Step 2707, it is judged whether the function call flag F is "1" (Step 2708). If the flag F is "1", the loop processing contains a function call and the invariant expression cannot be transferred. In this case, the processing returns to Step 2702. When the flag F is not "1", the reading position for the syntax file is returned to the initial position of the loop (Step 2709). Then, referring to the loop variable status table 410, the invariant expressions consisting of expressions with invariant values including the assignment destination variables of the assignment expressions containing variables whose values may change in repetitions are transferred out of the loop (Step 2710).
Referring now to the flowchart of FIG. 30, the procedure of the invariant expression transfer (Step 2710) is described below.
Firstly, a syntax for one line is read (Step 3001). Then, it is judged whether the read syntax represent the end of loop statements (Step 3002). If it represents the end of loop statements, the invariant expression transfer is terminated. If the read statement does not represent the end of loop statements, then it is judged whether the read syntax represent an assignment statement (Step 3003). If it does not represent an assignment statement, the processing returns to step 3001. On the other hand, if the read statement represent an assignment statement, the change 414 column of the loop variable status table 410 is referred to and it is judged whether the change data is "0" for all variables (Step 3004).
If the change data is "0" for all variables registered to the change column 414 of the loop variable status table 410, the result of this assignment statement does not change in repetition. The syntax of the assignment statement is transferred out of the loop statement before return to Step 3001 (Step 3005).
On the other hand, when there is a variable with a value other than "0", the value of its assignment destination variable is also changed. "1" is entered to the change column 414 corresponding to the variable name of the assignment destination variable before return to Step 3001 (Step 3006).
Until the and of loop statements, the above invariant expression transfer procedure (Steps 3001 to 3006) is repeated to move some invariant expressions. After that, the processing returns to Step 2702 in FIG. 27.
Thus, the processing by the loop invariant expression transfer section 131 is repeated until arrival at the end of syntax file.
FIGS. 31 and 32 show examples of loop invariant expression transfer results using a conventional complier to achieve optimization by transferring the loop invariant expressions as described above. FIG. 31 shows the processing result when a source program 1001 consisting of loop statements containing function calls as shown in FIG. 11 is input to a conventional complier. Referring to FIG. 31, the loop invariant expression transfer result for the loop block 1005 of the source program 1001 is a syntax 1601.
FIG. 32 shows the processing result when a source program 1101 including the definition of asynchronously operating interrupt function as shown in FIG. 21 (hereinafter referred to the asynchronous interrupt function) is input. Referring to FIG. 32, the loop invariant expression transfer result for the loop block 1105 of the source program 1101 is a syntax 1701.
When the loop invariant expressions are transferred for a source program including the definition of the asynchronous interrupt function, incorrect transfer may occur. According to the syntax 1701 as the result of loop invariant expression transfer in FIG. 32, transfer of the loop invariant expressions is suppressed here.
Note that the above loop optimization is described with referring to pages 398 to 429 of the above-mentioned reference.
When using the conventional compiler optimizing device and its method as described above, if a function call is made in the loop, the device cannot recognize which variable is changed in the function and cannot identify the invariant expressions, and the loop invariant expressions are not transferred at all. This results in a drawback that the optimization cannot be made sufficiently.
Further, when the source program contains an asynchronous interrupt function, the variables to be updated are not recognized in the invariant expression detection and the loop invariant expressions including the above variables may be incorrectly transferred out of the loop. To prevent such transfer, it is necessary to suppress the optimization by loop invariant expression transfer. This results in a drawback of a reduced optimization efficiency.